package data.structure.binarytree;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.List;

/**
 * @ClassName: BinarySearchTree1
 * @Description:
 * @Author: qiaopengxiang
 * @Date: 2022/6/29 16:29
 */
public class BinarySearchTree1 {
    private static NodeTree nodeTree;

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(20,22,1,9,12,18,1,2,3);
        list.forEach(e->{
            insert(e);
        });
        System.out.println(JSON.toJSONString(nodeTree));

        NodeTree.inOrder(nodeTree);
    }

    public static void insert(int data){
       if (nodeTree==null){
           nodeTree = new NodeTree(data);
           return;
       }
       NodeTree p = nodeTree;
       while (p!=null){
           if (data>p.data){
               if (p.right==null){
                   p.right = new NodeTree(data);
                   return;
               }
               p = p.right;
           }else {
               if (p.left == null){
                   p.left = new NodeTree(data);
                   return;
               }
               p = p.left;
           }
       }
   }

   public static void del(int data){
        NodeTree p  = nodeTree;
        NodeTree pp = null;
        while (p!=null && p.data!=data){
            pp = p;
            if (data>p.data){
                p = p.right;
            }else {
                p = p.left;
            }
        }
        if (p==null){
            return;
        }
        if (p.right!=null && p.left!=null){
            NodeTree minp = p;
            NodeTree minpp = null;
            while (minp.left!=null){
                minpp = minp;
                minp = minp.left;
            }
            p.data = minp.data;
            p = minp;
            pp = minpp;
        }


        NodeTree child = null;
        if (p.left!=null){
            child = p.left;
        }else if (p.right!=null){
            child = p.right;
        }

        if (pp == null){
            nodeTree = child;
        }else if (pp.left == p){
            pp.left = child;
        }else if (pp.right ==p){
            pp.right = child;
        }

   }


   public static Integer find(int data){
        NodeTree p = nodeTree;
        while (p!=null){
            if (data>p.data){
                p = p.right;
            }else if (data<p.data){
                p = p.left;
            }else {
                return p.data;
            }
        }
        return null;
   }

}
